class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        n = len(s)
        st = []
        s = [ord(c) - ord('a') for c in list(s)]
        st = s
        flag = False
        while st[-1] + 1 < k:
            st[-1] += 1
            if (n > 1 and st[-1] == st[-2]) or (n > 2 and st[-1] == st[-3]):
                continue
            else:
                flag = True
                break
        if not flag:
            st.pop()
        if not flag:
            while st:
                m = len(st)
                flag = False
                while st[-1] + 1 < k:
                    st[-1] += 1
                    if (m > 1 and st[-1] == st[-2]) or (m > 2 and st[-1] == st[-3]):
                        continue
                    else:
                        flag = True
                        break
                if not flag:
                    st.pop()
                else:
                    break
        if flag:
            while len(st) < n:
                m = len(st)
                for c in range(k):
                    if (m > 0 and st[-1] == c) or (m > 1 and st[-2] == c):
                        continue
                    else:
                        st.append(c)
                        break
            st = [chr(c + ord('a')) for c in st]
            return ''.join(st)
        else:
            return ''

        
data = Solution()
# s = 'abc'
# k = 8
# print(data.smallestBeautifulString(s, k))
s = 'dc'
k = 4
print(data.smallestBeautifulString(s, k))